package LeetCode;


/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}18:25
 */
public class LeetCode5 {
    //最长回文字符串
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2){
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // s.charAt()每次都会检查数组的下标越界，因此先转换其他字符数组
        char[] chars = s.toCharArray();

        // 枚举所有长度大于 1 的子串，charArray[i...j]
        for (int i = 0; i < len - 1; i++){
            for (int j = i + 1; j < len; j++){
                if (j - i + 1 > maxLen && validPalindromic(chars, i, j)){
                    maxLen = j - i + 1;// 回文子串的长度
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLen);// 因为这是左闭右开的，所以maxLen要 + 1才能包含完
    }

    private boolean validPalindromic(char[] chars, int left, int right) {
        while (left < right){
            if (chars[left] != chars[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 动态规划法
    /*
    第 1 步：定义状态
dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。

第 2 步：思考状态转移方程
在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：


dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
说明：

「动态规划」事实上是在填一张二维表格，由于构成子串，因此 i 和 j 的关系是 i <= j ，因此，只需要填这张表格对角线以上的部分。

看到 dp[i + 1][j - 1] 就得考虑边界情况。

边界条件是：表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。

这个结论很显然：j - i < 3 等价于 j - i + 1 < 4，即当子串 s[i..j] 的长度等于 2 或者等于 3 的时候，其实只需要判断一下头尾两个字符是否相等就可以直接下结论了。

如果子串 s[i + 1..j - 1] 只有 1 个字符，即去掉两头，剩下中间部分只有 1 个字符，显然是回文；
如果子串 s[i + 1..j - 1] 为空串，那么子串 s[i, j] 一定是回文子串。
因此，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下结论，dp[i][j] = true，否则才执行状态转移。

第 3 步：考虑初始化
初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true 。

事实上，初始化的部分都可以省去。因为只有一个字符的时候一定是回文，dp[i][i] 根本不会被其它状态值所参考。

第 4 步：考虑输出
只要一得到 dp[i][j] = true，就记录子串的长度和起始位置，没有必要截取，这是因为截取字符串也要消耗性能，记录此时的回文子串的「起始位置」和「回文长度」即可。

第 5 步：考虑优化空间
因为在填表的过程中，只参考了左下方的数值。事实上可以优化，但是增加了代码编写和理解的难度，丢失可读和可解释性。在这里不优化空间。

注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。

大家能够可以自己动手，画一下表格，相信会对「动态规划」作为一种「表格法」有一个更好的理解。
     */

    public String longestPalindrome2(String s) {
        // 特判
        int len = s.length();
        if (len < 2){
            return s;
        }
        int maxLen = 1;
        int begin = 0;

        // dp[i][j] 表示 s[i....j]是否为回文串
        boolean[][] dp = new boolean[len][len];
        char[] chars = s.toCharArray();

        // 初始化动态规划数组
        for (int i = 0; i < len; i++){
            dp[i][i] = true;
        }

        for (int j = 1; j < len; j++){
            for (int i = 0; i < j; i++){
                if (s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    if (j - i < 3){// 这个时候的情况是两个相同的字符之间只有一个字符这个时候绝对是回文
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];// 判断两个字符之间是否是回文是则这[i....j]之间都是回文
                    }
                }
                if (dp[i][j] && (j - i + 1) > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLen);
    }

    // 3中心扩展法 因此中心扩散法的思路是：
    // 遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
    // 、如果传入重合的索引编码，进行中心扩散，此时得到的回文子串的长度是奇数；
    //
    //2、如果传入相邻的索引编码，进行中心扩散，此时得到的回文子串的长度是偶数。
    public String longestPalindrome3(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0,1);
        // 中心位置枚举到 len - 2即可
        for (int i = 0; i < len - 1; i++){
            String oddStr = centerSpread(s,i,i);// 长度为奇数的情况
            String evenStr = centerSpread(s,i,i + 1);// 长度为偶数的情况
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen){
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }
    private String centerSpread(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0 && j < len){
            if (s.charAt(i) == s.charAt(j)){// 这里就是扩散 与 最开始的暴力解法相反
                i--;
                j++;
            }else {
                break;
            }
        }
        // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j 因为左闭右开所以j就不用管了
        return s.substring(i + 1,j);
    }
    public static void main(String[] args) {
        System.out.println(new LeetCode5().longestPalindrome2("babad"));
    }

}
